package com.sakura.动态规划;

import java.util.Arrays;

public class Code01_斐波那契 {

    // 递归-》动态规划入门 -》从顶到底
    public int fib1(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);
        return process(n, dp);
    }

    private int process(int n, int[] dp) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        if (dp[n] != -1) return dp[n];
        int answer = process(n - 1, dp) + process(n - 2, dp);
//        dp[n] = answer % 1000000007; // LCR 126. 斐波那契数
        dp[n] = answer;
        return answer;
    }

    // 从底到顶
    public int fib2(int n) {
        if (n == 0 || n == 1) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[n] = dp[n - 1] + dp[n - 2];
        }
        return dp[n];
    }
}
